//
//  LinkedListRealized.c
//  LinkedList
//
//  Created by Xavier on 2023/10/9.
//

#include "LinkedListRealized.h"
//初始化链表
ListNode ListInit()
{
    ListNode phead = BuySListNode(0);
    phead->next = NULL;
    
    return phead;
}

// 动态申请一个节点
ListNode BuySListNode(SLTDateType x) {
    ListNode newNode = (ListNode)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("malloc is err!\n");
        exit(-1);
    }
    newNode->data = x;
    newNode->next = NULL;
    
    return newNode;
}

// 单链表打印
void SListPrint(ListNode phead) {
    ListNode cur = phead->next;
    while (cur != NULL) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

// 单链表尾插
void SListPushBack(ListNode phead, SLTDateType x) {
    ListNode newNode = BuySListNode(x);
    if (phead->next == NULL) {
        phead->next = newNode;
    }else {
        ListNode last = phead->next;
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = newNode;
    }
}

// 单链表的头插
void SListPushFront(ListNode phead, SLTDateType x) {
    ListNode newNode = BuySListNode(x);
    ListNode next = phead->next;
    phead->next = newNode;
    newNode->next = next;
}

// 单链表的尾删
void SListPopBack(ListNode phead) {
    ListNode cur = phead->next;
    while (cur->next->next != NULL) {
        cur = cur->next;
    }
    ListNode last = cur->next;
    last = NULL;
    free(last);
    cur->next = NULL;
}

// 单链表头删
void SListPopFront(ListNode phead) {
    ListNode cur = phead->next;
    phead->next = cur->next;
    free(cur);
}

// 单链表查找
SListNode* SListFind(ListNode phead, SLTDateType x) {
    ListNode cur = phead->next;
    while (cur) {
        if (cur->data == x) {
            return cur;
        }else {
            cur = cur->next;
        }
    }
    return NULL;
}

// 单链表在pos位置之前插入x
void SListInsert(ListNode phead, ListNode pos, SLTDateType x) {
    ListNode newNode = BuySListNode(x);
    ListNode cur = phead->next;
    if (phead->next == pos) {
        ListNode tmp = pos;
        phead->next = newNode;
        newNode->next = tmp;
    }else {
        while (cur) {
            if (cur->next == pos) {
                ListNode tmp = pos;
                cur->next = newNode;
                newNode->next = tmp;
                break;
            }else {
                cur = cur->next;
            }
        }
    }
}

// 单链表删除pos位置的值
void SListErase(ListNode phead, ListNode pos) {
    ListNode cur = phead->next;
    if (phead->next == pos) {
        phead->next = phead->next->next;
        free(pos);
    }else {
        while (cur) {
            if (cur->next == pos) {
                ListNode tmp = pos->next;
                cur->next = tmp;
                free(pos);
                break;
            }else {
                cur = cur->next;
            }
        }
    }
}

// 合并两个链表(有序)
//思路：
//1、遍历1和2中的元素 用while 结束条件一方为空
//2、依次取1中和2中元素对比 2大于1 哪就插入1后面 反之cur1++
//3、判断哪一个为空 如果1空2没空 2直接插入1的后面 如果1没空2空直接返回 如果都空也直接返回
SListNode* Combine(ListNode phead1, ListNode phead2) {
    ListNode cur1 = phead1->next;
    ListNode cur2 = phead2->next;
    
    ListNode res = ListInit();
    ListNode resTmp = res;
    while (cur1 && cur2) {
        if (cur1->data >= cur2->data) {
            ListNode tmp = cur2->next;
            resTmp->next = cur2;
            cur2 = tmp;
            resTmp = resTmp->next;
        }else{
            ListNode tmp = cur1->next;
            resTmp->next = cur1;
            cur1 = tmp;
            resTmp = resTmp->next;
        }
    }
    if (cur1 == NULL && cur2 != NULL) {
        resTmp->next = cur2;
    }else if (cur2 == NULL && cur1 != NULL) {
        resTmp->next = cur1;
    }
    
    return res;
}

// 冒泡排序
//void Bubble(ListNode phead) {
//    ListNode cur = phead->next;
//    int count = 0;
//    while (cur) {
//        ++count;
//        cur = cur->next;
//    }
//
//}
